
#ifndef __ui_base_tree_node_model_h__
#define __ui_base_tree_node_model_h__

#pragma once

#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
#include "base/memory/scoped_vector.h"
#include "base/observer_list.h"
#include "base/string16.h"

#include "tree_model.h"

namespace ui
{

    // TreeNodeModel and TreeNodes provide an implementation of TreeModel around
    // TreeNodes.
    //
    // TreeNodes own their children, so that deleting a node deletes all
    // descendants.
    //
    // TreeNodes do NOT maintain a pointer back to the model. As such, if you
    // are using TreeNodes with a TreeNodeModel you will need to notify the observer
    // yourself any time you make any change directly to the TreeNodes. For example,
    // if you directly invoke set_title on a node it does not notify the observer,
    // you will need to do it yourself. This includes the following methods: Add,
    // Remove and set_title. TreeNodeModel provides cover methods that mutate the
    // TreeNodes and notify the observer. If you are using TreeNodes with a
    // TreeNodeModel use the cover methods to save yourself the headache.
    //
    // The following example creates a TreeNode with two children and then
    // creates a TreeNodeModel from it:
    //
    // TreeNodeWithValue<int>* root = new TreeNodeWithValue<int>();
    // root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 1"), 0));
    // root->Add(new TreeNodeWithValue<int>(ASCIIToUTF16("child 2"), 1));
    // TreeNodeModel<TreeNodeWithValue<int> > model(root);
    //
    // Two variants of TreeNode are provided here:
    //
    // . TreeNode itself is intended for subclassing. It has one type parameter
    //   that corresponds to the type of the node. When subclassing use your class
    //   name as the type parameter, eg:
    //   class MyTreeNode : public TreeNode<MyTreeNode> .
    // . TreeNodeWithValue is a trivial subclass of TreeNode that has one type
    //   type parameter: a value type that is associated with the node.
    //
    // Which you use depends upon the situation. If you want to subclass and add
    // methods, then use TreeNode. If you don't need any extra methods and just
    // want to associate a value with each node, then use TreeNodeWithValue.
    //
    // Regardless of which TreeNode you use, if you are using the nodes with a
    // TreeView take care to notify the observer when mutating the nodes.

    // TreeNode -------------------------------------------------------------------

    template<class NodeType>
    class TreeNode : public TreeModelNode
    {
    public:
        TreeNode() : parent_(NULL) {}

        explicit TreeNode(const string16& title)
            : title_(title), parent_(NULL) {}

        virtual ~TreeNode() {}

        // Adds |node| as a child of this one, at |index|.
        virtual void Add(NodeType* node, int index)
        {
            DCHECK(node);
            DCHECK_GE(index, 0);
            DCHECK_LE(index, child_count());
            // If the node has a parent, remove it from its parent.
            NodeType* parent = node->parent_;
            if(parent)
            {
                parent->Remove(node);
            }
            node->parent_ = static_cast<NodeType*>(this);
            children_->insert(children_->begin()+index, node);
        }

        // Removes |node| from this node and returns it. It's up to the caller to
        // delete it.
        virtual NodeType* Remove(NodeType* node)
        {
            typename std::vector<NodeType*>::iterator i =
                std::find(children_->begin(), children_->end(), node);
            DCHECK(i != children_.end());
            node->parent_ = NULL;
            children_->erase(i);
            return node;
        }

        // Removes all the children from this node. This does NOT delete the nodes.
        void RemoveAll()
        {
            for(size_t i=0; i<children_->size(); ++i)
            {
                children_[i]->parent_ = NULL;
            }
            children_->clear();
        }

        // Returns the parent node, or NULL if this is the root node.
        const NodeType* parent() const { return parent_; }
        NodeType* parent() { return parent_; }

        // Returns true if this is the root node.
        bool is_root() const { return parent_ == NULL; }

        // Returns the number of children.
        int child_count() const { return static_cast<int>(children_->size()); }

        // Returns true if this node has no children.
        bool empty() const { return children_.empty(); }

        // Returns the number of all nodes in the subtree rooted at this node,
        // including this node.
        int GetTotalNodeCount() const
        {
            int count = 1; // Start with one to include the node itself.
            for(size_t i=0; i<children_->size(); ++i)
            {
                count += children_[i]->GetTotalNodeCount();
            }
            return count;
        }

        // Returns the node at |index|.
        const NodeType* GetChild(int index) const
        {
            DCHECK_GE(index, 0);
            DCHECK_LT(index, child_count());
            return children_[index];
        }
        NodeType* GetChild(int index)
        {
            return const_cast<NodeType*>(
                static_cast<const NodeType&>(*this).GetChild(index));
        }

        // Returns the index of |node|, or -1 if |node| is not a child of this.
        int GetIndexOf(const NodeType* node) const
        {
            DCHECK(node);
            typename std::vector<NodeType*>::const_iterator i =
                std::find(children_->begin(), children_->end(), node);
            return i!=children_->end() ?
                static_cast<int>(i-children_->begin()) : -1;
        }

        // Sets the title of the node.
        void set_title(const string16& title) { title_ = title; }

        // TreeModelNode:
        virtual const string16& GetTitle() const { return title_; }

        // Returns true if this == ancestor, or one of this nodes parents is
        // ancestor.
        bool HasAncestor(const NodeType* ancestor) const
        {
            if(ancestor == this)
            {
                return true;
            }
            if(!ancestor)
            {
                return false;
            }
            return parent_ ? parent_->HasAncestor(ancestor) : false;
        }

    protected:
        std::vector<NodeType*>& children() { return children_.get(); }

    private:
        // Title displayed in the tree.
        string16 title_;

        // This node's parent.
        NodeType* parent_;

        // This node's children.
        ScopedVector<NodeType> children_;

        DISALLOW_COPY_AND_ASSIGN(TreeNode);
    };

    // TreeNodeWithValue ----------------------------------------------------------

    template<class ValueType>
    class TreeNodeWithValue : public TreeNode<TreeNodeWithValue<ValueType> >
    {
    public:
        TreeNodeWithValue() {}

        explicit TreeNodeWithValue(const ValueType& value)
            : ParentType(string16()), value(value) {}

        TreeNodeWithValue(const string16& title, const ValueType& value)
            : ParentType(title), value(value) {}

        ValueType value;

    private:
        typedef TreeNode< TreeNodeWithValue<ValueType> > ParentType;

        DISALLOW_COPY_AND_ASSIGN(TreeNodeWithValue);
    };

    // TreeNodeModel --------------------------------------------------------------

    // TreeModel implementation intended to be used with TreeNodes.
    template<class NodeType>
    class TreeNodeModel : public TreeModel
    {
    public:
        // Creates a TreeNodeModel with the specified root node. The root is owned
        // by the TreeNodeModel.
        explicit TreeNodeModel(NodeType* root) : root_(root) {}
        virtual ~TreeNodeModel() {}

        NodeType* AsNode(TreeModelNode* model_node)
        {
            return static_cast<NodeType*>(model_node);
        }

        void Add(NodeType* parent, NodeType* node, int index)
        {
            DCHECK(parent && node);
            parent->Add(node, index);
            NotifyObserverTreeNodesAdded(parent, index, 1);
        }

        NodeType* Remove(NodeType* parent, NodeType* node)
        {
            DCHECK(parent);
            int index = parent->GetIndexOf(node);
            NodeType* delete_node = parent->Remove(node);
            NotifyObserverTreeNodesRemoved(parent, index, 1);
            return delete_node;
        }

        void NotifyObserverTreeNodesAdded(NodeType* parent, int start, int count)
        {
            FOR_EACH_OBSERVER(TreeModelObserver,
                observer_list_, TreeNodesAdded(this, parent, start, count));
        }

        void NotifyObserverTreeNodesRemoved(NodeType* parent, int start, int count)
        {
            FOR_EACH_OBSERVER(TreeModelObserver,
                observer_list_, TreeNodesRemoved(this, parent, start, count));
        }

        void NotifyObserverTreeNodeChanged(TreeModelNode* node)
        {
            FOR_EACH_OBSERVER(TreeModelObserver,
                observer_list_, TreeNodeChanged(this, node));
        }

        // TreeModel:
        virtual NodeType* GetRoot()
        {
            return root_.get();
        }

        virtual int GetChildCount(TreeModelNode* parent)
        {
            DCHECK(parent);
            return AsNode(parent)->child_count();
        }

        virtual NodeType* GetChild(TreeModelNode* parent, int index)
        {
            DCHECK(parent);
            return AsNode(parent)->GetChild(index);
        }

        virtual int GetIndexOf(TreeModelNode* parent, TreeModelNode* child)
        {
            DCHECK(parent);
            return AsNode(parent)->GetIndexOf(AsNode(child));
        }

        virtual TreeModelNode* GetParent(TreeModelNode* node)
        {
            DCHECK(node);
            return AsNode(node)->parent();
        }

        virtual void AddObserver(TreeModelObserver* observer)
        {
            observer_list_.AddObserver(observer);
        }

        virtual void RemoveObserver(TreeModelObserver* observer)
        {
            observer_list_.RemoveObserver(observer);
        }

        virtual void SetTitle(TreeModelNode* node, const string16& title)
        {
            DCHECK(node);
            AsNode(node)->set_title(title);
            NotifyObserverTreeNodeChanged(node);
        }

    private:
        // The observers.
        ObserverList<TreeModelObserver> observer_list_;

        // The root.
        scoped_ptr<NodeType> root_;

        DISALLOW_COPY_AND_ASSIGN(TreeNodeModel);
    };

} //namespace ui

#endif //__ui_base_tree_node_model_h__